11291. Distributing the money

 

Huseyn and his younger brother found a wallet with n banknotes on the street. Since the owner of the money could not be found, they decided to divide the money among themselves. They divided the money among themselves so that everyone got the same amount of money. At this time, there could be the least amount of money that could be left. Huseyn took this money because he is the older brother.

Determine the amount of money that Hussein got.

 

Input. The first line contains an integer n (1 ≤ n ≤ 500) – the number of banknotes in the wallet. Each of the following lines contains one positive integer value ci – the value of the i-th banknote (in manats). It is known that c1 + ... + cn ≤ 105.

 

Output. Print the amount of money that Huseyn got.

 

Sample input 1

Sample output 1

5

4

2

3

1

10

10

 

 

Sample input 2

Sample output 2

4

3

17

2

19

22

 

 

SOLUTION

dynamic programming

 

Algorithm analysis

Let s1 be Huseyn’s current sum, s2 his brother’s current sum. We assume that s1 > s2. If it suddenly becomes s1 > s2, then we simply change the sums between the brothers.

Declare an array dp such that dp[i] contains the largest amount of money such that it can be given to Huseyn and his brother to get s1 – s2 = i. Note that in this case dp[i] = s1 + s2. For example, for the first test:

·        dp[0] = 20: Huseyn = {1, 2, 3, 4}, brother = {10}, (1 + 2 + 3 + 4) – 10 = 0;

·        dp[1] = 19: Huseyn = {10}, brother = {2, 3, 4}, 10 – (2 + 3 + 4) = 1;

·        dp[2] = 20: Huseyn = {1, 10}, brother = {2, 3, 4}, (1 + 10) – (2 + 3 + 4) = 2;

·        dp[3] = 17: Huseyn = {10}, brother = {3, 4}, (10) – (3 + 4) = 3;

For example, it is impossible to distribute an amount greater than 17 to the brothers so that the difference between their amounts is 3.

 

Initialize the array dp with values -1 (dp[i] = -1 means that it is impossible to distribute banknotes so that the difference between the amounts of the brothers was i). Initially set dp[0] = 0.

We start to process the banknotes sequentially. Let (i – 1) banknotes have already been processed, the current one is the banknote number i with the value ci.

Iterate over the elements of the array dp. Consider a cell dp[j] for which s1 – s2 = j and dp[j] = s1 + s2.

1.     Let’s give a banknote number i to Huseyn. Then the given amount of money will become s1 + s2 + ci = dp[j] + ci, and the difference between the amounts of the brothers become (s1 + ci) – s2 = j + ci. If the sum of dp[j] + ci is greater than dp[j  + ci], then the value of dp[j  + ci] should be updated:

dp[j + ci] = max(dp[j + ci], dp[j] + ci)

2.     Let’s give a banknote number i to Hussein's brother. Then the given amount of money become s1 + s2 + ci = dp[j] + ci, and the difference between the amounts of the brothers become s1 – (s2 + ci) = j – ci. If the sum dp[j] + ci is greater than dp[j  – ci], then the value of dp[j  – ci] should be updated. However, it may turn out that j – ci < 0. In this case, the brothers exchange money, and we take the difference by absolute value:

dp[| j – ci |] = max(dp[| j – ci |], dp[j] + ci)

 

After processing all the banknotes, dp[0] stores the largest amount that can be evenly distributed among the brothers. The rest is given to Huseyn. Let sum be the sum of all available money. Then Hussein will get dp[0] / 2 + (sum – dp[0]).

 

Example

Consider n = 3 banknotes with denominations {3, 5, 2}. Consider how the state of the dp array be changed while the banknotes are processed.

 

Consider the array processing for the last banknote ci = 2.

·        Banknote is given to Huseyn, iterate from left to right:

 

·        Banknote is given to Huseyn’s brother, iterate from right to left:

 

To get the final result, find the maximum among the corresponding cells of the temp arrays:

 

Algorithm realization

Read the number of banknotes n.

 

scanf("%d", &n);

 

Initialize the arrays with the value of -1.

 

#define MAX 100005

dp = vector<int>(MAX, -1);

tmp_dp = vector<int>(MAX, -1);

dp[0] = tmp_dp[0] = 0;

 

In the variable sum find the total amount of money.

 

sum = 0;

for (i = 0; i < n; i++)

{

 

Read the value of the i-th banknote c. Add this value to the total amount sum.

 

  scanf("%d", &c);

  sum += c;

 

Give a banknote with value c to Huseyn’s brother. Iterate from right to left.

 

for (j = MAX - 1; j >= 0; j--)

  if (dp[j] != -1)

    tmp_dp[abs(j - c)] = max(tmp_dp[abs(j - c)], dp[j] + c);

 

Give a banknote with value c to Huseyn. Iterate from left to right.

 

for (j = 0; j < MAX - c; j++)

  if (dp[j] != -1)

    tmp_dp[j + c] = max(tmp_dp[j + c], dp[j] + c);

 

Copy the contents of tmp_dp to dp.

 

  dp = tmp_dp;

}

 

Print the answer.

 

printf("%d\n", dp[0] / 2 + (sum - dp[0]));